/*
 * Created on 15 mars 2005 by Tudor.Ionescu@supelec.fr
 */
package clustering.implementations;
import clustering.framework.*;
import java.util.*;
/**
 * @author Tudor.Ionescu@supelec.fr
 * Implementation of the K-Means clustering method.
 * See http://www-2.cs.cmu.edu/~awm/tutorials/kmeans.html for details.
 */
public class KMEANSTreeConstructor implements IClusterTreeConstructor{
    public int K = 0;
    public String ConstructXMLTree(double [][] dDistanceMatrix){
        if(K==0){
            // K has not been initialized
            // let K be the LOG of length(dDistanceMatrix)
            K = (int)Math.round(Math.log(dDistanceMatrix.length));
        }
        int n = dDistanceMatrix.length;
        int [] centroids = new int[K];
        for(int i=0;i<K;i++)centroids[i] = -1;
        double [] min_distances = new double[K];
        int [][] clusters = new int[K][n];
        int [] cent_count = new int[K];

        // initial choice of centroids
        double [] initial_sum = new double[dDistanceMatrix.length];
        for(int i=0;i<dDistanceMatrix.length;i++){
            for(int j=0;j<dDistanceMatrix.length;j++){
                if(i!=j){
                    initial_sum[i] += dDistanceMatrix[i][j];
                }
            }
        }
        for(int i=0;i<K;i++){
            int min_index = -1;
            double min_value = Double.MAX_VALUE;
            for(int j=0;j<dDistanceMatrix.length;j++){
                if(min_value > initial_sum[j]){
                    min_value = initial_sum[j];
                    min_index = j;
                }
            }
            centroids[i]=min_index;
            initial_sum[min_index] = Double.MAX_VALUE;
        }
        
        ArrayList HistoryAL = new ArrayList();
        while(!CentroidsRepeat(centroids,HistoryAL)){
            HistoryAL.add(centroids.clone());
            for(int i=0;i<K;i++){
                cent_count[i] = 0;
            }
            // cluster the elements around the centroids 
            for(int i=0;i<n;i++){
                // determine to which centroid i will be assigned
                int my_centroid = -1;
                double min_dist = Double.MAX_VALUE;
                for(int j=0;j<K;j++){
                    if(dDistanceMatrix[i][centroids[j]] < min_dist){
                        min_dist = dDistanceMatrix[i][centroids[j]];
                        my_centroid = j;
                    }
                }
                clusters[my_centroid][cent_count[my_centroid]++]=i;
            }
            // choose the new centroids
            for(int i=0;i<centroids.length;i++){
                if(cent_count[i]>0){
                    centroids[i] = SelectCentroid(centroids[i],clusters[i],dDistanceMatrix,cent_count[i]);
                }
                min_distances[i] = min_tot_dist;
            }
        }

        // generate the XML tree
        String xmlTree = "<node step=\"0\" dist=\"0\">";
        for(int i=0;i<centroids.length;i++){
        	if(cent_count[i]>0){
	            xmlTree += "<node step=\""+(i+1)+"\" dist=\""+min_distances[i]+"\">";
	            for(int j=0;j<cent_count[i];j++){
	                xmlTree += "<node id=\""+clusters[i][j]+"\"/>";
	            }
	            xmlTree += "</node>";
        	}
        }
        xmlTree += "</node>";
        return xmlTree;
    }
    double min_tot_dist = Double.MAX_VALUE;
    int SelectCentroid(int c, int [] clusters, double [][] dm, int c_count){
        min_tot_dist = Double.MAX_VALUE;
        int min_elem = -1;        
        for(int i=0;i<c_count;i++){
            double tot_dist = 0;
            for(int j=0;j<dm.length;j++){
                tot_dist += dm[i][j];
            }
            if(min_tot_dist > tot_dist){
                min_tot_dist = tot_dist;
                min_elem = i; 
            }
        }
        return clusters[min_elem];
    }
    boolean CentroidsRepeat(int [] centroids, ArrayList HistoryAL){
        for(int i=0;i<HistoryAL.size();i++){
            int [] old_centroids = (int [])HistoryAL.get(i);
            boolean differ = false;
            for(int j=0;j<old_centroids.length;j++){
                if(old_centroids[j]!=centroids[j])differ = true;
            }
            if(!differ)return true;
        }
        return false;
    }
        
    int [] GenerateCentroids(){
        Random rand = new Random(100000);
        ArrayList al = new ArrayList();
        int [] r_list = new int[K];
        int count = 0;
        while(count < K){
            int r = rand.nextInt();
            try{
                Thread.sleep(1);
            }catch(Exception e){
                // nothing to do
            }
            boolean ok = true;
            for(int i=0;i<r_list.length;i++){
                if(r_list[i] == r)ok = false;
            }
            
        }
        return null;
    }
}
